package com.zwj.interview.二分查找;

/**
 * @Author: Zwj
 * @Date: 2023/2/13 13:25
 */
public class 旋转数组的最小数字 {
    /**
     * 目标数组是有序的，那么旋转后就变成两部分有序的子数组拼接在一起了
     *
     * 可以将这个旋转的数组看作是前后两个有序的子数组, 设置指针mid = (l + r) / 2.
     * 1.当选取的中间值 mid 所对应的值大于 l 所对应的值时,说明此时 mid 还在第一有序的数组中,而我们所要求解的最小值是在第二个有序数组的第一个位置,此时也就是在 mid 的后面,我们就将 l 移到 mid 所在的位置.
     * 2.当 r 所对应的值大于 mid 所对应的值时,说明最小值可能是 mid 所对应的值或者在 mid 的前面,我们将 r移到 mid 所在的位置.
     * 3.若r所对应的值等于mid所对应的值时，此时减少区间缩小范围。最后 l 所在的位置就是最小值的位置,直接返回即可
     */
    public int minNumberInRotateArray(int[] array) {
        if (array.length == 0) {
            return 0;
        }
        int low = 0;
        int high = array.length - 1;
        while (low < high) {
            //这是特殊情况，旋转数组的左边小于右边，说明最左边的就是最小的值
            if (array[low] < array[high]) {
                return array[low];
            }
            int mid = (low + high) / 2;
            //中间的值大于左边的，说明mid还在第一个有序子数组中，需要移动low指针
            if (array[mid] > array[low]) {
                low = mid + 1;
                //中间值小于最右边，说明最小值可能是中间值或者在中间的左边，那么移动右边的指针
            } else if (array[mid] < array[high]) {
                high = mid;
            } else {
                low++;
            }
        }
        return array[low];

    }
}